A public-key data communication system may be used to transfer information between a pair of correspondents. At least part of the information exchanged is enciphered by a predetermined mathematical operation by the sender and the recipient may perform a complementary mathematical operation to decipher the information.
Each correspondent has a private key and a public key that is mathematically related to the private key. The relationship is such that it is not feasible to determine the private key from knowledge of the public key. The keys are used in the transfer of data, either to encrypt data that is to be transferred or to attach a signature to allow verification of the authenticity of the data.
For encryption, one correspondent uses the public key of the recipient to encrypt the message and sends it to the recipient. The recipient then uses her private key to decipher the message.
A common key may also be generated by combining one parties public key with the other parties private key. It is usual in such cases to generate new private and corresponding public keys for each communication session, usually referred to as session keys or ephemeral keys, to avoid the long-term keys of the parties being compromised.
The exchange of messages and veneration of the public keys may therefore involve significant computation involving exponentiation when the cryptographic system utilizes in Z*p, the finite field of integers mod p where p is a prime or the analogous operation of point multiplication when the system utilizes an elliptic curve. In an elliptic curve system, an ephemeral key pair is obtained by generating a secret integer, k and performing a point multiplication in the seed point Q to provide the ephemeral public key kQ. Similarly, the generation of a common ephemeral session key will require multiplication of a public key kaQ, which is a point on the curve, with a secret integer kb of the other correspondent so that point multiplication is again required.
A similar procedure is used to sign a message except that the sender applies his private key to the message. This permits any recipient to recover and verify the message using the senders public key.
Various protocols exist for implementing such a scheme and some have been widely used. In each case, however, the sender is required to perform a computation to sign the information to be transferred and the receiver is required to perform a computation to verify the signed information.
In a typical implementation a signature component s has the form:s=ae+k (mod n)where; in an elliptic curve crypto system,                P is a point on the underlying curve which is a predefined parameter of the system;        k is a random integer selected as a short term private or session key;        R=kip is the corresponding short term public key;        a is the long term private key of the sender;        Q=aP is the senders corresponding public key;        e is a secure hash, such as the SHA-1 hash function, of a message m and the short term public key R; and        n is the order of the curve.        
The sender sends to the recipient a message including m, s, and R and the signature is verified by computing the value R1=(sP−eQ) which should correspond to R. If the computed values correspond then the signature is verified.
In order to perform the verification it is necessary to compute the point multiplications to obtain sP and eQ, each of which is computationally complex. Where the recipient has adequate computing, power this does not present a particular problem but where the recipient has limited computing power, such as in a secure token or a “Smart card” application, the computations may introduce delays in the verification process.
Key generation and signature protocols may therefore be computationally intensive. As cryptography becomes more widely used there is an increasing demand to implement cryptographic systems that are faster and that use limited computing power, such as may be found on a smart card or wireless device.
Elliptic curve cryptography (ECC) provides a solution to the computation issue. ECC permits reductions in key and certificate size that translates to smaller memory requirements, and significant cost savings. ECC can not only significantly reduce the cost, but also accelerate the deployment of smart cards in next-generation applications. Additionally, although the ECC algorithm allows for a reduction in key size, the same level of security as other algorithms with larger keys is maintained.
However, there is still a need to perform faster calculations on the keys so as to speed up the information transfer while maintaining a low cost of production of cryptographic devices.
Computing multiples of a point on an elliptic curve is one of the most frequent computations performed in elliptic curve cryptography. One method of speeding up such computations is to use tables of precomputed multiples of a point. This technique is more useful when a point is known beforehand. However, there are cases when multiples of previously unknown points are required (for example, in ECDSA verification). Thus there is a need for a system and method for facilitating point multiplications.